package com.company;

import java.util.*;

public class Solution {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while(sc.hasNextInt()){
            int money = sc.nextInt();
            money/=10;
            int num = sc.nextInt();
            Good[] goods = new Good[num];
            Map<Good, List<Good>> masters = new HashMap<>();
            for (int i = 0; i < num; i++) {
                int price = sc.nextInt();
                int weight = sc.nextInt() * price;
                price/=10;
                int parentIndex = sc.nextInt();
                goods[i] = new Good(price, weight, parentIndex);
                if (goods[i].getParentIndex() == 0){
                    masters.put(goods[i], new ArrayList<>());
                }
            }

            for (int i = 0; i < goods.length; i++) {
                if (goods[i].getParentIndex() != 0){
                    masters.get(goods[goods[i].getParentIndex() - 1]).add(goods[i]);
                }
            }
            int[] pw = new int[money + 1];
            for (Good m : masters.keySet()) {
                for (int j = money; j >= 1; j--) {
                    if (m.getPrice() <= j){
                        pw[j] = Math.max(pw[j], pw[j - m.getPrice()] + m.getWeight());
                        List<Good> childs = masters.get(m);
                        for (Good child : childs) {
                            if (child.getPrice() + m.getPrice() <= j){
                                pw[j] = Math.max(pw[j], pw[j - m.getPrice() - child.getPrice()] + m.getWeight() + child.getWeight());
                            }
                        }
                        if (childs.size() == 2){
                            Good c1 = childs.get(0);
                            Good c2 = childs.get(1);
                            if (c1.getPrice() + c2.getPrice() + m.getPrice() <= j){
                                pw[j] = Math.max(pw[j], pw[j - m.getPrice() - c1.getPrice() - c2.getPrice()] + m.getWeight() + c1.getWeight() + c2.getWeight());
                            }
                        }
                    }
                }
            }
            System.out.println(pw[money]);
        }

    }

    static class Good {
        private int price;
        private int weight;
        private int parentIndex;

        public Good(int price, int weight, int parentIndex) {
            this.price = price;
            this.weight = weight;
            this.parentIndex = parentIndex;
        }

        public int getPrice() {
            return price;
        }

        public void setPrice(int price) {
            this.price = price;
        }

        public int getWeight() {
            return weight;
        }

        public void setWeight(int weight) {
            this.weight = weight;
        }

        public int getParentIndex() {
            return parentIndex;
        }

        public void setParentIndex(int parentIndex) {
            this.parentIndex = parentIndex;
        }
    }
}